package com.lsa.letcode.the3.substr;

public class Solution {
	public int lengthOfLongestSubstring(String s) {
		return longest(s).length();
	}
	
	public String longest(String s) {
		if (s.isEmpty()) {
			return "";
		}
		int[] longest = longestImpl(s);
		return s.substring(longest[0], longest[1]+1);
	}
	
	private int[] longestImpl(String s) {
		int[] coords = new int[2];
		boolean[] hasRepetition = new boolean[2<<8];
		
		int i = 0;
		int j = 0;
		int n = s.length();
		int max = 0;
		
		while(j < n) {
			if (hasRepetition[s.charAt(j)]) {
				if (max < j - i) {
					coords[0] = i;
					coords[1] = j - 1;
					max = j - i;
				}
				
				while(s.charAt(i) != s.charAt(j)) {
					hasRepetition[s.charAt(i)] = false;
					i++;
				}
				i++;
			}
			else {
				hasRepetition[s.charAt(j)] = true;
			}
			j++;
		}
		
		if (max < j - i) {
			coords[0] = i;
			coords[1] = j - 1;
		}
		
		return coords;
	}
}